The present invention relates to an improved apparatus and method, for real-time decoding, or decompressing, a sequence of compressed words which are structured to have non-uniform lengths. More specifically, the present invention relates to a so-called run-length decoder with an improved structure, so as to effectively contain a corrupted code word within its own length and thus keeping it from further propagation during the real-time decoding process. The method disclosed in the present invention is most advantageous for decompressing multimedia data, which are typically vast in size but have become an important everyday item in today""s digital age. Another advantage of the present invention is that the error containment is achieved during the decoding process without requiring major additional computational efforts, and thus can be implemented with low-end machines in a very cost-effective manner.
Multimedia, or image, data such as those used in CD, DVD, MP3, and eventually digital TV, have become increasingly popular in today""s computer and communication systems. Because of the vast amount of data involved, which create a very heavy burden to the memory storage space and/or the transmission bandwidth, data compression is typically required so as to reduce the memory storage and/or bandwidth requirement. As a result, multimedia data are typically compressed before they are stored in the memory or transferred into the communication channel. These compressed data must be de-compressed, or decoded, before they can be put is use. In order to achieve real-time or near-real-time decoding, the decoding algorithm must be relatively simple, and must be done on a sequential basis. Batch programs such as MPEG, JPEG, etc. require relatively large buffer space, and may not be adaptable for a wide variety of machines.
In order to maximize the data compression efficiency, the compressed codes typically do not have a uniform length. This can cause problems in that if one coded (compressed) word is corrupted due to noise in the storage media or communication channel, the decoding of the entire data can be affected rendering it useless. One of the ways to ameliorate this problem is to implement a line-based compression rule, which compresses the image data on a line-by-line basis, and inserts a line_end_code at the end of each line of codes. Thus, if a code is corrupted, it will be contained in the line containing the same. The entire line will be ignored, but the rest of the image data is designed to remain unaffected.
One of the most frequently used line-based compression methods is called run-length compression method. Basically with this method the compressed code comprises three portions: (1) the range of number of pixels (or bits) having the same value; (2) the exact number of the pixels contained in the un-compressed code; (3) the pixel data. Both portions (1) and (2) are of variable lengths. Portion (1), which also provides information regarding the total length of the code word, typically contains an even number of zeros, and Portion (2) contains the exact number of bits required to represent the number of pixels within the range indicated in Portion (1) which have the same value. Portion (1) can be omitted if the number of same value pixels is very small (typically from 1 to 3). An example of the run-length compression method is described below. This example is based on a maximum 16-bit compressed code, which is also the length of the data stream being processed by the decoder.
(A) The Compressed Code Represents 1 to 3 Pixels with the Same Pixel Value (Code Word 0)
These pixels are represented by the following code word:
(B) The Compressed Code Represents 4 to 15 Pixels with the Same Pixel Value (Code Word 1)
These pixels are represented by the following code word:
(C) The Compressed Code Represents 16 to 63 Pixels with the Same Pixel Value (Code Word 2)
These pixels are represented by the following code word:
(D) The Compressed Code Represents 64 to 255 Pixels with the Same Pixel Value (Code Word 3)
These pixels are represented by the following code word:
(E) The Compressed Code Represents Same Pixels to the End of Line (Code Word 4)
These pixels are represented by the following code word:
Code Word 4 is also considered as the line_end-code.
If the byte alignment is not accomplished when the description of pixels on one line is completed, a dummy data of 4 bits 0000b is inserted for adjustment.
When the image data are coded according to the above-mentioned example, the decoder typically comprises a shifter, a code word comparator, a shift_number generator, and a code interpreter. Because this method implements a 16-bit decoding operation, the shifter requests and receives 16-bit data stream from a data bus, typically a 32-bit data bus. The code word comparator checks the number of leading even-numbered zeros in the first portion of the code word to determine the number of bits in the second portion, i.e., after the leading zeros in the first portion. Since the bit number in the third portion is fixed, i.e., always two bits, the total number of bits in the code word being compared in the comparator can be determined. The comparator then sends the bit count data to the shift_number generator, which sends a new_shift_number (which is the same as the bit count of the code word being compared) to the shifter. The shifter then shifts the data stream stored therein according the new_shift_number, and a new 16-bit data stream is sent to the code word comparator from the shifter. The shifter also sends a request for a new 32-bit image data when the data stored therein is about to be exhausted due to the bit shifting.
The length of each code word according to the run-length method is not fixed. Different repeat pixel patterns will result in different lengths of the resulting code words. Each line is terminated with a line_end_code, this compression rule is line-based, i.e., it compresses the image date on a line by line basis. Due to noise that may be present in the storage medium or communication channel, the code word may be corrupted. If the corruption occurs in the first portion, i.e., the portion which contains leading zeros to determine the length of the code word, not only this particular code word will not be interpreted correctly, all the image data that follow will also be affected.
The primary object of the present invention is to develop an improved decoding method and device to decompress image data that have been compressed according to the run-length technique. More specifically, the primary object of the present invention is to develop an improved run-length based decoding method which will prevent the propagation of a corrupted code word into the rest of the image data by containing the error within the length of the code.
According to the run-length compression method an image data is compressed by grouping pixels with the same value into a compressed code word. Each compressed code word comprises three portions:
(1) 0 to N-m bits to indicate the number of bits corresponding to the range of the number of pixels having the same value (in the uncompressed image data), where N is the number of bits of the data stream being decoded and m is the number of bits taken up by the pixel data. The range of the number of repeat pixels, as represented by the bit number of portion (1) also tells the number of bits reserved for Portion (2), which is dictated by the maximum possible number of repeat pixels within the range indicated by Portion (1).
(2) The exact number of the (repeat) pixels contained in the un-compressed code, if portion (1) takes up N-m bits, then no space is reserved for Portion (2).
(3) The pixel data, m bits, typically 2 bits.
Portion (1) typically contains an even number of zeros, and Portion (2) contains the number of bits required to represent the maximum number of repeat pixels within the range indicated in Portion (1). Both portions (1) and (2) are of variable lengths. The value represented in Portion (2), of course, is a variable, depending on the exact number of repeat pixels. According to an embodiment of the run-length method, portion (1) can be omitted if the number of same value pixels is very small. If portion (1) takes up N-m bits, then the code word means the same pixels continue until the end of each line.
In one of the preferred embodiment of the present invention, the maximum number of bits for a code word is 16 bits (i.e., the entire length of the data stream), and the compressed code word is represented by one of five code patterns, containing 0 (exactly 1 to 3 repeating pixels), 2 (4 to 15 repeating pixels), 4 (16 to 63 repeating pixels), 6 (64 to 255 repeating pixels), and 14 (repeating pixels to the end of line) leading zeros, respectively. During the decoding process, the shifter of the present invention has six outputs, each going into one of six code comparators. These six comparators of the present invention are structured as follows:
Code Comparator 1: In this comparator, no assumption is made to the code word pattern, the number of bits in the first portion is established by reading leading zeros, then the number of same pixels is establish from the second portion. If the latter agrees with the first, then the code word is not corrupted, and an output signal find_code is turned active.
Code Comparator 2: In this comparator, it assumes that there are no leading zeros (i.e., assuming 1 to 3 same pixels) in the first portion, and it checks the first two bits to verify if the number of same pixels matches this assumption. If the assumption is valid then an output signal current_is_code0 is made active, along with the Code Word 0 type code word.
Code Comparator 3: In this comparator, it assumes that there two leading zero (i.e., assuming 4 to 15 same pixels) in the first portion of the code word and resets the corresponding bits accordingly (i.e., resetting the first two bits to zero). Then it checks values in the next four bits to verify if the number of same pixels so represented matches this assumption. If the assumption is valid then an output signal current_is_code1 is made active, along with the reset code word (Code Word 1).
Code Comparator 4: In this comparator, it assumes that there four leading zero (i.e., assuming 16 to 63 same pixels) in the first portion of the code word and resets the corresponding bits accordingly (i.e., resetting the first four bits to zero). Then it checks values in the next six bits to verify if the number of same pixels so represented matches this assumption. If the assumption is valid then an output signal current_is_code2 is made active, along with the reset code word (Code Word 2).
Code Comparator 5: In this comparator, it assumes that there six leading zero (i.e., assuming 64 to 255 same pixels) in the first portion of the code word and resets the corresponding bits accordingly (i.e., resetting the first six bits to zero). Then it checks values in the next eight bits to verify if the number of same pixels so represented matches this assumption. If the assumption is valid then an output signal current_is_code3 is made active, along with the reset code word (Code Word 3).
Code Comparator 6: In this comparator, it assumes that there fourteen leading zero (i.e., assuming same pixels all the way to the end of line) in the first portion and resets the corresponding bits accordingly (i.e., resetting the first fourteen bits to zero). This is a default, or catch-all, option, no comparison needs to be made. This assumption is valid if none of the other code comparators sends out an active output signal, and an output signal current_is_code4 is made active, along with the reset code word (Code Word 4).
Output signals from the six code comparators are sent to a Code Type Arbitrator, which is essentially a multiplexer, a properly reset code word is then selected along with the number of bits it should have taken up. The reset code word is sent to a Code Interpreter, and the number of bits is read by a Shift_Number_Generater, which subsequently sends aNew_Shift_Number to the shifter, and a new 16-bit input is output from the shifter to all of the six Code Word Comparators.
Alternatively, the resetting of the data stream to correspond to each of the assumed Code_Word_Patterns can be done in the shifter.
With the method disclosed in the present invention, if a code word is corrupted, the main objective is not to try to determine what the correct code may be. Rather, the main objective is to determine its correct word length, so that the error will be contained within that length, and will not be propagated and thus affecting the rest of the data. Another advantage of the present invention is that the error containment is achieved during the decoding process without requiring major additional computational efforts, and thus can be implemented in a very cost-effective manner. For example, the entire operation can be pipe-lined so that the operation which involves a plurality of comparators will not result in increased computation cycles.